

/**
 *
 * 动态规划
 * 我们比较 db(i) = max( db(i-1)+a(i),a(i))
 * 不过其实没有那么复杂，我们在遍历一次的时候我们只要抓住一个点
 * 就是如果连续起来的子数组和小于0，就抛弃掉，因为小于0加什么数字都会变小，从而抛弃，从不小于0的位置开始
 * 时间复杂度为n
 * @param array arr
 * @return obj 返回结果对象
 *
 * */
function DP(arr) {

    var sum=0,max=0;
    var start=0,end=0;
    for(var i=0;i<arr.length;i++){
        sum+=arr[i];
        if( sum > max ){
            end=i;
            max = sum;
        }else if(sum<0){ // 和小于0，抛弃，加什么都是变小
            start=i+1;
            sum=0;
        }
    }
    return {
        max:max,
        start:start,
        end:end,
        subarr:arr.slice(start,end+1)
    };
}


// console.log(DP(arr));


exports.DP = DP;